package 剑指offer;

import java.util.ArrayList;
import java.util.List;

public class _34二叉树中和为某一值的路径 {
  public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
   }
}


    public List<List<Integer>> pathSum(TreeNode root, int target) {
        //结果集
        List<List<Integer>> result = new ArrayList<>();

        //待选结果
        List<Integer> list = new ArrayList<>();
        pathSumDFS(root, target, result, list);
        return result;

    }

    private void pathSumDFS(TreeNode root, int target, List<List<Integer>> result, List<Integer> list) {
        if(root == null){
            return;
        }
        //1.添加结果到待选结果中
        list.add(root.val);
        //2.条件更新，剪枝判定
        target -= root.val;
        if (root.left == null && root.right == null && target == 0){
            result.add(new ArrayList<Integer>(list));//注意深浅拷贝
        }
        //3.深度优先遍历子树
        pathSumDFS(root.left, target, result, list);
        pathSumDFS(root.right, target, result, list);
        //4.回退
        list.remove(list.size()-1);
    }
}
